import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class NM3 {
    //使用非递归方法进行实现快速排序；
    public static void quickSort(int[] array){
        int start=0;
        int end=array.length-1;
        Deque<Integer> stack=new LinkedList<>();
        int paint=partition(array,start,end);
        if(paint>start+1){
            stack.push(start);
            stack.push(paint-1);
        }
        if(paint<end-1){
            stack.push(paint+1);
            stack.push(end);
        }
        while(!stack.isEmpty()){
            end=stack.pop();
            start=stack.pop();
            paint=partition(array,start,end);
            if(paint>start+1){
                stack.push(start);
                stack.push(paint-1);
            }
            if(paint<end-1){
                stack.push(paint+1);
                stack.push(end);
            }
        }
    }
    public static int partition(int[] array,int left,int right){
       //挖坑法进行查找基准值；
        int temp=array[left];
       while(left<right){
           while(left<right&&array[right]>=temp){
               right--;
           }
           array[left]=array[right];
           while(left<right&&array[left]<=temp){
               left++;
           }
           array[right]=array[left];
       }
       array[left]=temp;
       return left;
    }
    public static void main(String[] args){
        int[] array={6,1,2,7,9,3,4,5,10,8};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

}
